SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Abstract cell complex</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Abstract cell complex</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In mathematics, an <b>abstract cell complex</b> is an abstract set with <a href="Alexandrov_topology" title="Alexandrov topology">Alexandrov topology</a> in which a non-negative integer number called <a href="Dimension" title="Dimension">dimension</a> is assigned to each point. The complex is called “abstract” since its points, which are called “cells”, are not subsets of a <a href="Hausdorff_space" title="Hausdorff space">Hausdorff space</a> as is the case in Euclidean and <a href="CW_complex" title="CW complex">CW complexes</a>. Abstract cell complexes play an important role in <a href="Image_analysis" title="Image analysis">image analysis</a> and <a href="Computer_graphics" title="Computer graphics">computer graphics</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p>The idea of abstract cell complexes <sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> (also named abstract cellular complexes) relates to <a href="Johann_Benedict_Listing" title="Johann Benedict Listing">J. Listing</a> (1862) <sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> and <a href="Ernst_Steinitz" title="Ernst Steinitz">E. Steinitz</a> (1908).<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Also A.W Tucker (1933),<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> K. Reidemeister (1938),<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> P.S. Aleksandrov (1956) <sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> as well as R. Klette and A. Rosenfeld (2004) <sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> have described abstract cell complexes. E. Steinitz has defined an abstract cell complex as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=(E,B,dim)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C=(E,B,dim)}</annotation>

</semantics>

</math></span><img src="./4e8c45705a4a61167bc18edde5e4da813580fcfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.34ex; height:2.843ex;" alt="{\displaystyle C=(E,B,dim)}" loading="lazy"></span> where <i>E</i> is an <b>abstract</b> set, <i>B</i> is an asymmetric, irreflexive and transitive binary relation called the <b>bounding relation</b> among the elements of <i>E</i> and <i>dim</i> is a function assigning a non-negative integer to each element of <i>E</i> in such a way that if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(a,b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B(a,b)}</annotation>

</semantics>

</math></span><img src="./374a70e181eb94295f799038c2d3b81fbbef12ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.835ex; height:2.843ex;" alt="{\displaystyle B(a,b)}" loading="lazy"></span>, then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dim(a)<dim(b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dim(a)<dim(b)}</annotation>

</semantics>

</math></span><img src="./e197de275d0597967b1cac4c3aa23ca138c8c78e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.062ex; height:2.843ex;" alt="{\displaystyle dim(a)<dim(b)}" loading="lazy"></span>.

V. <a href="Vladimir_Antonovich_Kovalevsky" title="Vladimir Antonovich Kovalevsky">Kovalevsky</a> (1989) <sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> described abstract cell complexes for 3D and higher dimensions. He also suggested numerous applications to image analysis. In his book (2008) <sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> he suggested an axiomatic theory of locally finite <a href="Topological_spaces" class="mw-redirect" title="Topological spaces">topological spaces</a> which are generalization of abstract cell complexes. The book contains new definitions of topological balls and spheres independent of <a href="Metric_(mathematics)" class="mw-redirect" title="Metric (mathematics)">metric</a>, a new definition of <a href="Combinatorial_manifold" class="mw-redirect" title="Combinatorial manifold">combinatorial manifolds</a> and many algorithms useful for image analysis.

</p>

<div class="mw-heading mw-heading2"><h2 id="Basic_results">Basic results</h2></div>

<p>The topology of abstract cell complexes is based on a <a href="Partial_order" class="mw-redirect" title="Partial order">partial order</a> in the set of its points or cells.

</p><p>The notion of the abstract cell complex defined by E. Steinitz is related to the notion of an <a href="Abstract_simplicial_complex" title="Abstract simplicial complex">abstract simplicial complex</a> and it differs from a <a href="Simplicial_complex" title="Simplicial complex">simplicial complex</a> by the property that its elements are not <a href="Simplex" title="Simplex">simplices</a>: An <i>n</i>-dimensional element of an abstract complexes does not necessarily have <i>n</i>+1 zero-dimensional sides, and not each subset of the set of zero-dimensional sides of a cell is necessarily a cell. This is important since the notion of an abstract cell complexes can be applied to the two- and three-dimensional grids used in image processing, which is not true for simplicial complexes. A non-simplicial complex is a generalization which makes the introduction of cell coordinates possible: There are non-simplicial complexes which are Cartesian products of such "linear" one-dimensional complexes where each zero-dimensional cell, besides two of them, bounds exactly two one-dimensional cells. Only such Cartesian complexes make it possible to introduce such coordinates that each cell has a set of coordinates and any two different cells have different coordinate sets. The coordinate set can serve as a name of each cell of the complex which is important for processing complexes.

</p><p>Abstract complexes allow the introduction of classical topology (Alexandrov-topology) in grids being the basis of digital image processing. This possibility defines the great advantage of abstract cell complexes: It becomes possible to exactly define the notions of connectivity and of the boundary of subsets. The definition of dimension of cells and of complexes is in the general case different from that of simplicial complexes (see below).

</p><p>The notion of an abstract cell complex differs essentially from that of a CW-complex because an abstract cell complex is not <a href="Hausdorff_space" title="Hausdorff space">Hausdorff</a>. This is important from the point of view of computer science since it is impossible to explicitly represent a non-discrete Hausdorff space in a computer. (The neighborhood of each point in such a space must have infinitely many points).

</p><p>The book by <a href="Vladimir_Antonovich_Kovalevsky" title="Vladimir Antonovich Kovalevsky">V. Kovalevsky</a><sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> contains the description of the theory of <a href="Locally_finite_space" title="Locally finite space">locally finite spaces</a> which are a generalization of abstract cell complexes. A locally finite space <i>S</i> is a set of points where a subset of <i>S</i> is defined for each point <i>P</i> of <i>S</i>. This subset containing a limited number of points is called the <b>smallest neighborhood</b> of <i>P</i>. A binary neighborhood relation is defined in the set of points of the locally finite space <i>S</i>: The element (point) <i>b</i> is in the neighborhood relation with the element <i>a</i> if <i>b</i> belongs to the smallest neighborhood of the element <i>a</i>. New axioms of a locally finite space have been formulated, and it was proven that the space <i>S</i> is in accordance with the axioms only if the neighborhood relation is anti-symmetric and transitive. The neighborhood relation is the reflexive hull of the inverse bounding relation. It was shown that classical axioms of the topology can be deduced as theorems from the new axioms. Therefore, a locally finite space satisfying the new axioms is a particular case of a classical topological space. Its topology is a <a href="Poset_topology" title="Poset topology">poset topology</a> or <a href="Alexandrov_topology" title="Alexandrov topology">Alexandrov topology</a>.

An abstract cell complex is a particular case of a locally finite space in which the dimension is defined for each point. It was demonstrated that the dimension of a cell <i>c</i> of an abstract cell complex is equal to the length (number of cells minus 1) of the maximum bounding path leading from any cell of the complex to the cell <i>c</i>. The bounding path is a sequence of cells in which each cell bounds the next one. The book contains the theory of digital straight segments in 2D complexes, numerous algorithms for tracing boundaries in 2D and 3D, for economically encoding the boundaries and for exactly reconstructing a subset from the code of its boundary. Using the abstract cell complexes, efficient algorithms for tracing, coding and polygonization of boundaries, as well as for the edge detection, are developed and described in the book <sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Abstract_Cell_Complex_Digital_Image_Representation">Abstract Cell Complex Digital Image Representation</h2></div>

<p>A digital image may be represented by a 2D Abstract Cell Complex (ACC) by decomposing the image into its ACC dimensional constituents: points (0-cell), cracks/edges (1-cell), and pixels/faces (2-cell).

</p>

<p>This decomposition together with a coordinate assignment rule to unambiguously assign coordinates from the image pixels to the dimensional constituents permit certain image analysis operations to be carried out on the image with elegant algorithms such as crack <a href="Boundary_tracing" title="Boundary tracing">boundary tracing</a>, digital straight segment subdivision, etc. One such rule maps the points, cracks, and faces to the top left coordinate of the pixel. These dimensional constituents require no explicit translation into their own data structures but may be implicitly understood and related to the 2D array which is the usual data structure representation of a digital image. This coordinate assignment rule and the renderings of each cell incident to this image is depicted in the image at right.

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .portalbox{padding:0;margin:0.5em 0;display:table;box-sizing:border-box;max-width:175px;list-style:none}.mw-parser-output .portalborder{border:1px solid var(--border-color-base,#a2a9b1);padding:0.1em;background:var(--background-color-neutral-subtle,#f8f9fa)}.mw-parser-output .portalbox-entry{display:table-row;font-size:85%;line-height:110%;height:1.9em;font-style:italic;font-weight:bold}.mw-parser-output .portalbox-image{display:table-cell;padding:0.2em;vertical-align:middle;text-align:center}.mw-parser-output .portalbox-link{display:table-cell;padding:0.2em 0.2em 0.2em 0.3em;vertical-align:middle}@media(min-width:720px){.mw-parser-output .portalleft{margin:0.5em 1em 0.5em 0}.mw-parser-output .portalright{clear:right;float:right;margin:0.5em 0 0.5em 1em}}

/* end https://en.wikipedia.org/ */

</style>

<ul><li><a href="Simplicial_complex" title="Simplicial complex">Simplicial complex</a></li>

<li><a href="Cubical_complex" title="Cubical complex">Cubical complex</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Reinhard Klette: Cell complexes through time. <a rel="nofollow" class="external free" href="http://spie.org/Publications/Proceedings/Paper/10.1117/12.404813">http://spie.org/Publications/Proceedings/Paper/10.1117/12.404813</a></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">Listing J.: "Der Census räumlicher Complexe". <i>Abhandlungen der Königlichen Gesellschaft der Wissenschaften zu Göttingen</i>, v. 10, Göttingen, 1862, 97–182.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">Steinitz E.: "Beiträge zur Analysis". <i>Sitzungsbericht Berliner Mathematischen Gesellschaft</i>, Band. 7, 1908, 29–49.</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">Tucker A.W.: "An abstract approach to manifolds", Annals Mathematics, v. 34, 1933, 191-243.</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">Reidemeister K.: "Topologie der Polyeder und kombinatorische Topologie der Komplexe". Akademische Verlagsgesellschaft Geest & Portig, Leipzig, 1938 (second edition 1953)</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">Aleksandrov P.S.: Combinatorial Topology, Graylock Press, Rochester, 1956,</span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">Klette R. and Rosenfeld. A.: "Digital Geometry", Elsevier, 2004.</span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">Kovalevsky, V.: "Finite Topology as Applied to Image Analysis", <i>Computer Vision, Graphics and Image Processing</i>, v. 45, No. 2, 1989, 141–161.</span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.geometry.kovalevsky.de./">"Home"</a>. <i>geometry.kovalevsky.de</i>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text">V. Kovalevsky: "Geometry of Locally Finite Spaces". Editing house Dr. Bärbel Kovalevski, Berlin 2008. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-9812252-0-4</bdi>.</span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">Kovalevsky, V., Image Processing with Cellular Topology, Springer 2021, ISBN 978-981-16-5771-9.</span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-05" href="https://en.wikipedia.org/wiki/?title=Abstract_cell_complex&oldid=1298879592">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>